package slidingWindow;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author kunkun
 * @className LeetCode_438
 * @Description 给定两个字符串s和p，找到s中所有p的异位词子串，返回这些子串的起始索引
 * @date 2025/2/28 17:55
 */
public class LeetCode_438 {

    public List<Integer> findAnagrams(String s, String p) {
        return solution_1(s,p);
    }

    @Test
    public void test(){
        print(findAnagrams("cbaebabacd","abc"));
    }

    public static void print(List<Integer> list){
        for (Integer integer : list) {
            System.out.print(integer+" ");
        }
    }

    /**
    * @Description: 方法1：通过滑动窗口，对每个窗口逐个判断，时间复杂度：O（m*n）
    * @Author: kunkun
    * @Date:  2025/2/28 18:05
    * @Parameters:
    * @Return
    * @Throws
    */
    public static List<Integer> solution_1(String s, String p){
        //0. 定义输出结果
        ArrayList<Integer> list = new ArrayList<>();
        //1. 逐个判断窗口
        for (int i = 0; i <= s.length()-p.length(); i++) {
            if (checkConditionByArray(s,p,i)){
                list.add(i);
            }
        }
        return list;
    }

    //判断s中第index开始的字串和p是否满足异位词条件---使用map
    public static boolean checkConditionByMap(String s,String p,int index){
        //1. 提取字串
        String str = s.substring(index,p.length()+index); //左闭，右开
        //2. 将str添加到map中
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            //2.1 逐个添加到map中
            if (map.containsKey(str.charAt(i))){
                map.put(str.charAt(i),map.get(str.charAt(i))+1);
            }else {
                map.put(str.charAt(i),1);
            }
        }
        //3. 将p从map中删去
        for (int i = 0; i < p.length(); i++) {
            //2.1 逐个从map中删去
            if (map.containsKey(p.charAt(i))){
                int count = map.get(p.charAt(i));
                if (count==1){
                    map.remove(p.charAt(i));
                }else {
                    map.put(p.charAt(i),count-1);
                }
            }
        }
        //4. 返回结果
        return (map.size()==0);
    }
    
    //判断s中第index开始的字串和p是否满足异位词条件---使用array
    public static boolean checkConditionByArray(String s,String p,int index){
        //1. 提取字串
        String str = s.substring(index,p.length()+index); //左闭，右开
        int[] count = new int[26];
        //2. 将str添加到array中
        for (int i = 0; i < str.length(); i++) {
            count[str.charAt(i)-'a']++;
        }
        //3. 将p从array中删去
        for (int i = 0; i < p.length(); i++) {
            count[p.charAt(i)-'a']--;
        }
        //4. 返回结果
        boolean flag=true;
        for (int i = 0; i < count.length; i++) {
            if (count[i]!=0){
                flag=false;
            }
        }
        return flag;
    }


}
